package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

/**
 * @description:
 * 450. 删除二叉搜索树中的节点
 * 中等
 * 1.2K
 * 相关企业
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/5 15:38
 * @version:1.0
 */
public class 删除二叉搜索树中的节点 {
    public TreeNode deleteNode(TreeNode root, int key) {

        return deleteNodeDigui(root,key,null,true);

    }
    public TreeNode deleteNodeDigui(TreeNode root, int key,TreeNode parent,boolean isLeft){
        if(root == null){
            return root;
        }
        if(root.val == key){
            TreeNode thisNode = null;
            //删除当前节点
            /**
             *四种情况，1.左右孩子都为空，直接删除
             *2.左孩子为空，右孩子补位
             *3.右孩子为空，左孩子补位
             *4.左右都不为空，当前节点的左子树放置到右子树最左节点的左孩子上
             */
            if(root.left != null && root.right != null){
                //左右都不为空
                //updateNode(root.right,parent,isLeft);
                TreeNode firstLeefNode = getFirstNoLeftNode(root.right);
                //将当前节点的左子树更新为右子树第一个左孩子为空的节点
                updateNode(root.left,firstLeefNode,true);
                //将当前节点的右子树更新为父节点的子孩子
                updateNode(root.right,parent,isLeft);
                thisNode = root.right;
            }else if(root.left == null){
                updateNode(root.right,parent,isLeft);
                thisNode = root.right;
            }else{
                updateNode(root.left,parent,isLeft);
                thisNode = root.left;
            }
            //返回当前节点
            return thisNode;
        }else{
            deleteNodeDigui(root.left,key,root,true);
            deleteNodeDigui(root.right,key,root,false);
            return root;
        }
    }
    public void updateNode(TreeNode newNode,TreeNode parent,boolean isLeft){
        if(parent == null){
            return;
        }
        if(isLeft){
            parent.left = newNode;
        }else{
            parent.right = newNode;
        }
    }
    //寻找第一个左孩子为空的节点
    public TreeNode getFirstNoLeftNode(TreeNode node){
        if(node.left == null){
            return node;
        }

        return getFirstNoLeftNode(node.left);

    }
}
